package com.哈希表;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
 *
 * 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
 *
 * 例如:
 *
 * 输入:
 * A = [ 1, 2]
 * B = [-2,-1]
 * C = [-1, 2]
 * D = [ 0, 2]
 *
 * 输出:
 * 2
 *
 * 解释:
 * 两个元组如下:
 * 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
 * 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
 */
public class 四数相加2 {
    static class Solution {
        /**
         * 暴力法
         * @param A
         * @param B
         * @param C
         * @param D
         * @return
         */
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            int count = 0;
            int length  = A.length;
           for(int a = 0;a<length;a++){
               for(int b = 0;b<length;b++){
                   for(int c =0;c<length;c++){
                       for(int d = 0;d<length;d++){
                           int sum = A[a]+B[b]+C[c]+D[d];
                           if(sum == 0){
                               count ++ ;
                           }
                       }
                   }
               }
           }
            return count;
        }

        /**
         * a+b+c+d = 0 都可以用算式转换成  a+b = -(c+d)
         * @param A
         * @param B
         * @param C
         * @param D
         * @return
         */
        public int fourSumCount2(int[] A, int[] B, int[] C, int[] D) {
            Map<Integer, Integer> map = new HashMap<>();
            int count  = 0;
            int length = A.length;
            for(int a = 0;a<length;a++ ){
                for(int b = 0 ;b<length;b++){
                    int sum = A[a]+B[b];
                    map.put(sum,map.getOrDefault(sum,0)+1);
                }
            }
            for(int c = 0;c<length;c++){
                for(int d = 0;d<length;d++){
                    int sum = -(C[c]+D[d]);
                    if(map.containsKey(sum)){
                        count+=map.get(sum);
                    }
                }
            }

        return count;
        }


        public static void main(String[] args) {
            Solution solution = new Solution();


    int[] A = new int[]{8,-6,4,-17,0,-19,-12,-30,9,-12,-6,-18,6,-8,-26,-13,-3,-28,-17,-2,-17,-31,-5,-10,10,-18,-17,-24,-17,2,3,-31,-27,-27,-31,4,-17,9,-19,-18,-29,0,1,0,-21,8,5,-20,-7,-20,9,-31,-9,-17,-16,-18,3,9,-9,-23,-5,6,-17,-5,3,-10,-19,-31,-31,-30,-2,-1,-21,-25,-30,-30,-22,-29,0,5,-16,-31,-28,-9,-14,-24,-16,-20,-28,-23,-30,-32,-11,-32,-30,-27,3,-21,-17,-16}
       ,B= new int[]     {-16,0,-28,-15,-30,-8,-3,-23,-2,-30,-28,-14,-24,-28,-27,-3,1,-15,-26,5,-18,9,-12,-23,-2,10,-30,-2,-22,-10,0,6,0,-3,9,-9,3,-24,7,4,10,-12,-6,-7,-30,-13,0,-22,-5,-25,-8,-28,-7,-13,-1,-26,-1,-4,0,10,-30,-21,-23,-11,4,4,-8,-23,-22,5,-20,-7,-29,-1,-7,9,-10,-17,-15,2,0,-20,-4,-30,-30,-31,-22,-21,-25,-5,-3,0,-13,-8,-18,-19,4,-5,-20,0}
       ,C=new int[]        {10,10,-14,-27,-13,2,4,1,-31,-1,-5,-23,10,-16,5,-6,-30,-14,-18,-9,-27,6,-28,-19,-9,6,-29,-17,-32,-15,4,-19,-27,-2,5,-25,-14,-18,-14,-17,-26,-6,-19,-17,-13,0,-32,-25,3,-4,-10,-17,-28,8,-29,-12,-25,-24,-5,-8,2,-22,-1,-6,-26,10,-31,9,-7,6,-21,-31,-31,-21,-25,-5,9,10,-6,5,-22,-9,-21,5,-8,-29,-8,10,-23,-18,-11,-1,-1,-18,8,-29,-23,-23,4,-29}
       ,D = new int[]             {7,-21,-3,-14,-18,4,10,5,-4,-17,-19,-3,2,-17,-4,5,-20,-11,3,-22,-19,1,0,-20,-3,0,-11,-24,-15,-26,2,6,-26,3,-3,-28,-5,-19,-13,-1,10,-12,-32,1,-6,-3,-3,-14,-11,-16,-23,0,-18,-6,10,-22,-1,-1,-20,-12,-14,-6,-24,10,-1,-7,-11,-25,-11,-7,9,-28,-17,-14,5,-30,-20,-1,6,4,-17,3,-14,-24,-16,-9,-32,-16,-27,-16,9,10,-16,-32,-18,-6,-20,-8,-1,-29}
        ;
            System.out.println(solution.fourSumCount2(A,B,C,D));
        }
    }
}
